import time
import math


def is_prime(n):
    """判断一个数是否为素数"""
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 只需检查到sqrt(n)即可
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

def generate_primes(max_limit):
    """生成指定范围内的所有素数"""
    primes = []
    for num in range(2, max_limit + 1):
        if is_prime(num):
            primes.append(num)
    return primes


def optimized_generate_primes(max_limit):
    """使用埃拉托斯特尼筛法生成素数（优化版本）"""
    if max_limit < 2:
        return []

    # 初始化筛子
    sieve = [True] * (max_limit + 1)
    sieve[0] = sieve[1] = False

    for current in range(2, int(math.sqrt(max_limit)) + 1):
        if sieve[current]:
            # 标记当前数的所有倍数为非素数
            for multiple in range(current * current, max_limit + 1, current):
                sieve[multiple] = False

    # 收集所有素数
    primes = [num for num, is_p in enumerate(sieve) if is_p]
    return primes


def print_primes(primes):
    """按每行5个的格式打印素数"""
    for i, prime in enumerate(primes):
        # 控制每行输出5个素数
        print(f"{prime:6}", end='')
        if (i + 1) % 5 == 0:
            print()
    print()  # 最后换行


if __name__ == "__main__":
    max_num = 20000

    # 测试普通方法性能
    start_time = time.time()
    primes_normal = generate_primes(max_num)
    normal_time = time.time() - start_time

    # 测试优化方法性能
    start_time = time.time()
    primes_optimized = optimized_generate_primes(max_num)
    optimized_time = time.time() - start_time

    # 输出结果（使用优化方法的结果）
    print(f"1~{max_num}之间的所有素数如下：")
    print_primes(primes_optimized)

    # 输出性能对比
    print(f"\n普通方法耗时: {normal_time:.6f}秒")
    print(f"埃拉托斯特尼筛法耗时: {optimized_time:.6f}秒")
    print(f"优化方法比普通方法快约{normal_time / optimized_time:.2f}倍")
    print(f"1~{max_num}之间共有{len(primes_optimized)}个素数")

    # 性能分析
    print("\n性能分析:")
    print("1. 普通方法中最耗时的是is_prime函数，特别是对于大数的判断")
    print("2. 优化方法使用埃拉托斯特尼筛法，避免了重复判断，大幅提高了效率")
    print("3. 优化思路：通过标记非素数而不是逐个判断，减少了重复计算")
